Surrogate regret bounds for generalized classification performance metrics

摘要

We consider optimization of generalized performance metrics for binaryclassification by means of surrogate losses. We focus on a class of metrics,which are linear-fractional functions of the false positive and false negativerates (examples of which include $F_{\beta}$-measure, Jaccard similaritycoefficient, AM measure, and many others). Our analysis concerns the followingtwo-step procedure. First, a real-valued function $f$ is learned by minimizinga surrogate loss for binary classification on the training sample. It isassumed that the surrogate loss is a strongly proper composite loss function(examples of which include logistic loss, squared-error loss, exponential loss,etc.). Then, given $f$, a threshold $\widehat{\theta}$ is tuned on a separatevalidation sample, by direct optimization of the target performance metric. Weshow that the regret of the resulting classifier (obtained from thresholding$f$ on $\widehat{\theta}$) measured with respect to the target metric isupperbounded by the regret of $f$ measured with respect to the surrogate loss.We also extend our results to cover multilabel classification and provideregret bounds for micro- and macro-averaging measures. Our findings are furtheranalyzed in a computational study on both synthetic and real data sets.